package Offer12;

/**
 * 矩阵中的路径
 * 给定一个m x n 二维字符网格board 和一个字符串单词word 。如果word 存在于网格中，返回 true ；否则，返回 false 。
 *
 * 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。
 * 同一个单元格内的字母不允许被重复使用。
 * @author 23737
 * @time 2021.10.26
 */
public class Test {
    public static void main(String[] args) {

    }
}

/**
 * 使用深搜来解决
 */
class Solution {
    public boolean exist(char[][] board, String word) {
        //先检查是否可以进行寻找（检查是否满足条件）
        if (board.length == 0 || board[0].length == 0 || board == null || word == null) { // 判断是否为空, 为空则直接返回false
            return false;
        }
        //获取二维矩阵的行数和列数
        int row = board.length;
        int colomn = board[0].length;
        //表示已经找到的字符串的数目
        int IsFind = 0;
        //记录是否可以走
        int[][] hs = new int[row][colomn];

        for (int i = 0; i < row; i++) {
            for (int j = 0; j < colomn; j++) {
                if (board[i][j] == word.charAt(IsFind)) {
                    hs[i][j]++;
                    if (IsFind == word.length() - 1 || SearchFind(i, j, IsFind + 1, board, word, hs)) {
                        return true;
                    }
                }
            }
        }
        return false;
    }

    private boolean SearchFind(int i, int j, int i1, char[][] board, String word, int[][] hs) {
        // 往上搜索
        if (i - 1 >= 0 && hs[i - 1][j] == 0 && board[i - 1][j] == word.charAt(i1)) {
            hs[i - 1][j] = hs[i][j] + 1;
            if (i1 == word.length() - 1 || SearchFind(i - 1, j, i1 + 1, board, word, hs)) {
                return true;
            }
        }
        // 往下搜索
        if (i + 1 < board.length && hs[i + 1][j] == 0 && board[i + 1][j] == word.charAt(i1)) {
            hs[i + 1][j] = hs[i][j] + 1; // 可以根据数组元素大小顺序模拟出路径
            if (i1 == word.length() - 1 || SearchFind(i + 1, j, i1 + 1, board, word, hs)) {
                return true;
            }
        }
        // 往左搜索
        if (j - 1 >= 0 && hs[i][j - 1] == 0 && board[i][j - 1] == word.charAt(i1)) {
            hs[i][j - 1] = hs[i][j] + 1;
            if (i1 == word.length() - 1 || SearchFind(i, j - 1, i1 + 1, board, word, hs)) {
                return true;
            }
        }

        // 往右搜索
        if (j + 1 < board[0].length && hs[i][j + 1] == 0 && board[i][j + 1] == word.charAt(i1)) {
            hs[i][j + 1] = hs[i][j] + 1;
            if (i1 == word.length() - 1 || SearchFind(i, j + 1, i1 + 1, board, word, hs)) {
                return true;
            }
        }
        hs[i][j] = 0;
        return false;
    }

}
